Relationen

Eine (n-stellige) Relation R zwischen Mengen M1,...,Mn ist eine Teilmenge des Kartesischen Produkts M1 ×

× Mn.

Wir spezialisieren sofort auf n = 2 (zweistellige Relationen) und schreiben R(a,b) oder aRb wenn < a,b > R.

Beispiel: Sei T die Menge aller Tierarten, F die Menge aller Fortbewegungsarten (schwimmen, fliegen, tauchen, ...). Dann ist

T × F > R = {< Schwan, fliegt >, < Schwan, schwimmt >, < Schwan, lauft >, ¨ < Karpfen,taucht >, < Fliege,fliegt >, ...}

eine mögliche Relation zwischen T (dem Argument- oder Definitionsbereich) von R und F (dem Wertebereich).

Im Beispiel hat ”Schwan“ mehrere Bilder und und ”fliegt“ mehrere Urbilder. In diesem Sinn ist die Relation eine Verallgemeinerung des Funktionsbegriffs.

Die inverse Relation R^-1 entsteht durch Vertauschung von Definitions- und Wertebereich und der Tupelelemente:

R -1 = {(b,a)|(a,b) (- R}.

Das Komplement einer Relation R zwischen M und N ist (M × N) \ R.

Beispiel: M = {1,2,3}, R

M × M. Relation “ist kleiner als”ist R = {< 1,2 >,< 1,3 >,< 2,3 >}. R ist dann ”ist nicht kleiner als“ oder ”ist größer oder gleich“, R^-1 ”ist größer als“.

Vokabeln

Sei R

M × M.

Wir reden jetzt also von Relationen zwischen Elementen ein und derselben Menge

R heißt

reflexiv: x M :< x,x > R.
irreflexiv: x M :< x,x > R.
symmetrisch: Mit < x,y > R gilt auch < y, x > R.
asymmetrisch: Mit < x,y > R gilt auch < y,x > R. (dies ist zu unterscheiden von ”nicht symmetrisch“; für nicht symmetrische Relationen impliziert < x,y > R nichts.)
antisymmetrisch: < y,x > R und < x, y > R impliziert x = y(Das muss nicht so sein: {< a,b >,< b,a >} ist eine völlig legale Relation, aber a b.)
transitiv: < x,y > R und < y,z > R impliziert < x,z > R.
intransitiv: < x,y > R und < y, z > R impliziert < x,z > R (die Begriffsbildung ist parallel zu reflexiv und asymmetrisch: Die einfache Verneinung wäre der Wegfall der Implikation, die Begriffe hier aber drehen den Schluss um).
konnex: x, y M :< x,y > R $\/$ < y,x > R.

Beispielsweise ist die Relation “=”reflexiv, symmetrisch und transitiv, die Relation “<”irreflexiv, asymmetrisch, transitiv und konnex, die Relation “<”reflexiv, asymmetrisch, antisymmetrisch, transitiv und konnex.

Markus Demleitner